/**
 * 插值查找函数
 * @param {Array} arr - 已排序的数组，必须是升序
 * @param {number} target - 要查找的目标值
 * @returns {number} - 返回目标值在数组中的索引，如果未找到则返回 -1
 */
function InsertSearch(arr, target) {
    if (arr.length === 0 || target < arr[0] || target > arr[arr.length - 1]) {
        return -1;
    }

    // 1. 确定最小下标和最大下标
    let low = 0;
    let high = arr.length - 1;
    let mid = 0;
    while (low <= high) {
        // 使用浮点数计算中间索引，防止溢出
        mid = Math.floor(((target - arr[low]) / (arr[high] - arr[low]) * (high - low)) + 0.5);

        // 2.1 查找到
        if (arr[mid] === target) {
            return mid;
        }
        // 2.2 目标值在 arr[mid] 右侧
        else if (arr[mid] < target) {
            low = mid + 1;
        }
        // 2.3 目标值在 arr[mid] 左侧
        else {
            high = mid - 1;
        }
    }
    return -1;
}

// 准备测试数据
let arr = [];
for (let i = 0; i < 1000; i++) {
    arr.push(i);
}
let target = 20;
console.log(InsertSearch(arr, target)); // 输出: 33
